package linked;
import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
public class Ex25 {
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head, end = head;
        ListNode pre = null, last = null, post = head, temp = null, tail = null;
        List<ListNode> heads = new ArrayList<>();
        int count;
        while (end != null) {
            count = 1;
            while (end.next != null) {
                if (count == k) break;
                count++;
                end = end.next;
            }
            //这轮的头结点
            heads.add(end);
    
            if (count < k) { //count不足k，表明最后一轮无法转化,返回第一轮的头结点
                return heads.get(0);
            }
            //下一轮的start
            last = end.next;
    
            //对start到end部分进行反转
            post = start;
            pre = last; //pre替换为下轮的首节点
            while (post != last) {
                temp = post.next;
                post.next = pre;
                pre = post;
                post = temp;
            }
            //上一轮连接到这一轮
            if (tail != null) {
                tail.next = end;
            }
    
            //start和end更新到下次的首节点
            tail = start;
            start = last;
            end = last;
        }
        return heads.get(0);
    }
    }

    @Test
    public void test() {
        for (int i = 0; i < 20; i++) {
            int[] nums = ArrayGenerator.getArray(100, 20);
        System.out.println(Arrays.toString(nums));
        System.out.println((int)(Math.random() * (nums.length / 4)) + 2);
        }
    }
}
